# Vector

[Vector](https://scala-lang.org/api/3.x/scala/collection/immutable/Vector.html) -
это индексируемая неизменяемая последовательность.
"Индексируемая" часть описания означает, что она обеспечивает произвольный доступ
и обновление за практически постоянное время,
поэтому можно быстро получить доступ к элементам `Vector` по значению их индекса,
например, получить доступ к `listOfPeople(123_456_789)`.

В общем, за исключением той разницы, что (а) `Vector` индексируется, а `List` - нет,
и (б) `List` имеет метод `::`, эти два типа работают одинаково.

Вот несколько способов создания `Vector`:

```dotty
val nums = Vector(1, 2, 3, 4, 5)
// nums: Vector[Int] = Vector(1, 2, 3, 4, 5)
val strings = Vector("one", "two")
// strings: Vector[String] = Vector("one", "two")
case class Person(name: String)
val people = Vector(
  Person("Bert"),
  Person("Ernie"),
  Person("Grover")
)
// people: Vector[Person] = Vector(
//   Person(name = "Bert"),
//   Person(name = "Ernie"),
//   Person(name = "Grover")
// )
```

Поскольку `Vector` неизменяем, в него нельзя добавить новые элементы.
Вместо этого создается новая последовательность,
с добавленными к существующему `Vector` в начало или в конец элементами.

Например, так элементы добавляются в конец:

```dotty
val a = Vector(1,2,3)
// a: Vector[Int] = Vector(1, 2, 3)
val b = a :+ 4
// b: Vector[Int] = Vector(1, 2, 3, 4)
val c = a ++ Vector(4, 5)
// c: Vector[Int] = Vector(1, 2, 3, 4, 5)
```

А так - в начало `Vector`-а:

```dotty
val a = Vector(1,2,3)
// a: Vector[Int] = Vector(1, 2, 3)
val b = 0 +: a
// b: Vector[Int] = Vector(0, 1, 2, 3)
val c = Vector(-1, 0) ++: a
// c: Vector[Int] = Vector(-1, 0, 1, 2, 3)
```

В дополнение к быстрому произвольному доступу и обновлениям,
`Vector` обеспечивает быстрое добавление в начало и конец.

> Подробную информацию о производительности `Vector` и других коллекций см. в
> [характеристиках производительности коллекций](https://docs.scala-lang.org/overviews/collections-2.13/performance-characteristics.html).

Наконец, `Vector` в цикле `for` используется точно так же, как `List`, `ArrayBuffer` или любая другая последовательность:

```dotty
val names = Vector("Joel", "Chris", "Ed")
// names: Vector[String] = Vector("Joel", "Chris", "Ed")
for name <- names do println(s"My name is $name")
// My name is Joel
// My name is Chris
// My name is Ed
```


Вектора представленны деревьями с высоким уровнем ветвления 
(уровень ветвления дерева или графа - это количество дочерних элементов у каждого узла). 
Каждый узел дерева содержит до 32-х элементов вектора или содержит до 32-х других узлов. 
Вектора с размером до 32-х элементов могут быть представлены одним узлом. 
Вектора с 32 * 32 = 1024 элементами могут быть представлены одним витком. 
Для векторов с \\(2^{15}\\) элементами достаточно двух переходов от корня дерева до конечного элемента узла, 
трех переходов - для векторов с \\(2^{20}\\) элементами, 
четырех переходов - для \\(2^{25}\\) элементами и пяти переходов для \\(2^{30}\\) элементами. 
Таким образом, для всех векторов разумных размеров выбор элемента включает до 5 простых выборок массивов. 
Именно это подразумевается, что доступ к элементам осуществляется с "практически постоянным временем".

Так же как и доступ к элементу, операция обновления в векторах занимает "практически" постоянное время. 
Добавление элемента в середину вектора может быть выполнено через копирование узла содержащего этот элемент 
и каждого ссылающегося на него узла, начиная от корня дерева. 
Это означает, что процесс обновления элемента создает от одного до пяти узлов, 
каждый из которых содержит до 32 элементов или поддеревьев. 
Это, конечно, дороже, чем просто обновление элемента в изменяемом массиве, 
но все же намного дешевле, чем копирование вообще всего вектора.

Поскольку вектора обладают хорошим балансом между быстрой случайной выборкой 
и быстрым случайным обновлением элементов, 
они используются в качестве реализации неизменяемых индексированных последовательностей:

```dotty
collection.immutable.IndexedSeq(1, 2, 3)
// res2: IndexedSeq[Int] = Vector(1, 2, 3)
```


---

**Ссылки:**

- [Scala3 book](https://docs.scala-lang.org/scala3/book/taste-collections.html)
- [Scala3 book, Collections Types](https://docs.scala-lang.org/scala3/book/collections-classes.html)
- [Scala, Immutable collections](https://docs.scala-lang.org/ru/overviews/collections-2.13/concrete-immutable-collection-classes.html)
